package edu.spbsu.nonsm00th.computgeom.chull.impl;

import edu.spbsu.nonsm00th.algorithms.sort.Sort;
import edu.spbsu.nonsm00th.computgeom.sort.impl.ComparatorD2Polar;
import edu.spbsu.nonsm00th.algorithms.sort.util.SortUtil;
import edu.spbsu.nonsm00th.computgeom.chull.ConvexHull;
import edu.spbsu.nonsm00th.computgeom.util.D2Util;
import edu.spbsu.nonsm00th.computgeom.util.DNUtil;
import edu.spbsu.nonsm00th.model.Point;
import edu.spbsu.nonsm00th.model.enums.Orientation;
import edu.spbsu.nonsm00th.util.Precondition;
import java.util.Collections;
import java.util.List;

/**
 * Realization of Graham convex hull algorithm.
 * Should be used only for 2-dimensional point lists.
 * 
 * @author mbuzdov
 */
public class D2GrahamConvexHull implements ConvexHull {

    private Sort<Point> sorter = SortUtil.getD2Sorter();

    public void convexHull(List<Point> list) {
        Precondition.argsNotNull(list);
        if (0 == list.size()) {
            return;
        }

        Point inner = D2Util.findInnerPoint(list);
        sorter.sort(list, new ComparatorD2Polar(inner));

        removeSames(list);
        int begin = DNUtil.findCartesianMinimumIndex(list);
        Collections.rotate(list, -begin);

        grahamScan(list);
    }

    private void removeSames(List<Point> list) {
        if (null == list) {
            return;
        }
        int i = 0;
        while (i + 1 < list.size()) {
            if (list.get(i).equals(list.get(i + 1))) {
                list.remove(i + 1);
            } else {
                i++;
            }
        }
    }

    private void grahamScan(List<Point> list) {
        int current = 0;
        int previous = getPreviousTo(current, list);
        boolean flag = false;
        while (0 != getNextTo(current, list) || !flag) {
            if (previous == getNextTo(current, list)) {
                flag = true;
            }
            if (current != getNextTo(getNextTo(current, list), list) &&
                    Orientation.UNDER == D2Util.getOrientation(
                    list.get(current),
                    list.get(getNextTo(current, list)),
                    list.get(getNextTo(getNextTo(current, list), list)))) {
                list.remove(getNextTo(current, list));
                current = getPreviousTo(current, list);
                previous = getPreviousTo(current, list);
            } else {
                current = getNextTo(current, list);
            }
        }
    }

    private int getPreviousTo(final int index, final List<Point> list) {
        if (index > 0) {
            return index - 1;
        }
        return list.size() - 1;
    }
    private int getNextTo(final int index, final List<Point> list) {
        if (index + 1 <= list.size() - 1) {
            return index + 1;
        }
        return 0;
    }

}
